1. Field of the Invention
The present invention relates to the field of computer memories. More particularly, the present invention relates to the field of First-In-First-Out memories for multi-processor computer systems.
2. Description of the Related Art
First-In-First-Out memories (FIFOs)are commonly used in electronic systems. FIFOs are used to transfer data between two electronic devices or modules where the data source (data writer) produces data asynchronously to a data sink's (data reader's) need for the data. The data is written into the FIFO by the writer as it is produced, and then read from the FIFO by the reader as the data is needed.
A FIFO is typically composed of a buffer where the data elements are stored, and descriptors which contain control information about the FIFO such as pointers to the storage locations where the next read or write operations should occur. An important consideration in the design of a FIFO is to prevent FIFO overflow and underflow conditions. A FIFO overflow occurs when the FIFO is full (all the buffer locations are used) and the writer attempts to insert a new data element. A FIFO underflow occurs when the FIFO is empty (there are no elements in the buffer) and the reader attempts to retrieve an element from the buffer. FIFO buffers may be implemented in many ways including arrays, linked lists and dedicated hardware memories. Similarly, FIFO descriptors may be software data structures or dedicated hardware circuits.
In many systems with multiple processors communicating among each other, each processor may have part or all of its memory accessible by other processors. Such memory will be referred to as shared memory, while processor memory that is not accessible for other processors will be called private memory. A subsystem, which includes a processor together with its private and shared memory, is typically interconnected with other subsystems by a bus. An example of such a bus is the industry standard Peripheral Component Interconnect (PCI) bus.
FIG. 1 shows a typical system having two electronic subsystem modules, each module including a processor and associated memory. A first module 10 which reads from a FIFO, and a second module 20 which writes to the FIFO, are connected via bus 30. Reader module 10 includes a processor 12, bus interface logic 14, private memory 16, and shared memory 18. Similarly, Writer module 20 includes a processor 22, bus interface logic 24, private memory 26, and shared memory 28. For each module, its shared memory is accessible by the other module. In such a system, only one subsystem may be the master of the bus at a given time. The master requests the bus, waits until the bus is granted, and then initiates a transaction resulting in data being transferred to one or more other subsystems. If another subsystem has data to transfer at the same time, that second subsystem has to wait until the current bus master terminates the transaction. The time elapsed between the bus request and the first element of data being transferred is called bus latency. The bus latency typically increases with the number of subsystems using the bus and the average length of a transaction.
The simplest implementation for a FIFO is to use dedicated hardware circuits. In this case, a write controller performs a write transaction to a fixed memory location. The hardware based FIFO manager stores the data in the order it was received and informs the writer when an overflow condition occurs via a discrete output from the FIFO. A read controller performs a read transaction from the FIFO mapped at a fixed memory location and the FIFO manager makes the data available at the FIFO output port from its internal storage, in the order it was put there by the writer. Examples of such FIFOs include fall-through FIFOs and RAM based FIFOs.
FIG. 2 illustrates a second way to implement a FIFO. In this implementation, both the FIFO buffer and the FIFO descriptor are implemented in shared memory. This implementation will be described further below.
In the discussion that follows the algorithms used to implement the FIFO will be described using the C programming language for illustration purposes. The actual implementation may employ a different language, assembly language, or a hardware FIFO manager. Similarly, the FIFO buffer will be described as a RAM-based array holding data elements, although other implementations are possible. In the example of FIG. 2, the FIFO is implemented in memory that is on-board to the writer electronic module. Alternatively, the FIFO could be implemented within shared memory on-board to the reader module, with appropriate changes to the read and write algorithms.
In a first conventional implementation A, the FIFO descriptor is composed of two pointers (a read pointer, RD, and a write pointer, WR) and two binary flags (a full flag and an empty flag). The corresponding C programming language type definition statement is: